package Algorithm.Dp;

import java.util.Map;
import java.util.TreeMap;

//https://leetcode-cn.com/problems/delete-and-earn/
//740. 删除并获得点数
public class Leetcode740_删除并获得点数 {
    class Solution {
        public int deleteAndEarn(int[] nums) {
            TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();

            for(int i = 0; i < nums.length; i++){
                map.put(nums[i], map.getOrDefault(nums[i], 0) + nums[i]);
            }

            nums = new int[map.size()];
            int index = 0;
            for(Map.Entry<Integer, Integer> entry : map.entrySet()){
                nums[index] = entry.getKey();
                index++;
            }

            int[] dp = new int[map.size()];

            if(map.size()==1){
                return nums[0];
            }
            dp[0] = map.getOrDefault(nums[0], 0);
            if(nums[1]==nums[0]+1){
                dp[1] = Math.max(dp[0], map.get(nums[1]));
            }else{
                dp[1] = dp[0] + map.get(nums[1]);
            }

            for(int i = 2; i < nums.length; i++){
                if(nums[i]==nums[i-1]+1){
                    dp[i] = Math.max(dp[i-2] + map.get(nums[i]), dp[i-1]);
                }else{
                    dp[i] = dp[i-1] + map.get(nums[i]);
                }
            }

            return dp[nums.length-1];
        }
    }
}
